package com.lw.leetcode.arr.b;

import java.util.ArrayList;
import java.util.List;

/**
 * 752. 打开转盘锁
 * 剑指 Offer II 109. 开密码锁
 *
 * @Author liw
 * @Date 2021/6/25 13:56
 * @Version 1.0
 */
public class OpenLock {
    public int openLock(String[] deadends, String target) {
        int[] arr = new int[10000];
        for (String deadend : deadends) {
            arr[Integer.parseInt(deadend)] = -1;
        }
        int t = Integer.parseInt(target);
        if (arr[0] == -1 || arr[t] == -1) {
            return -1;
        }
        if (t == 0) {
            return 0;
        }
        List<Integer> list = new ArrayList<>(10000);
        List<Integer> list2 = new ArrayList<>(10000);

        list.add(0);
        arr[0] = 1;
        int n = 2;
        while (!list.isEmpty()) {
            for (Integer value : list) {
                if (value == t) {
                    return n - 2;
                }
                int aa = find(value, 1000, 1);
                if (arr[aa] == 0) {
                    arr[aa] = n;
                    list2.add(aa);
                }
                aa = find(value, 1000, -1);
                if (arr[aa] == 0) {
                    arr[aa] = n;
                    list2.add(aa);
                }
                aa = find(value, 100, 1);
                if (arr[aa] == 0) {
                    arr[aa] = n;
                    list2.add(aa);
                }
                aa = find(value, 100, -1);
                if (arr[aa] == 0) {
                    arr[aa] = n;
                    list2.add(aa);
                }
                aa = find(value, 10, 1);
                if (arr[aa] == 0) {
                    arr[aa] = n;
                    list2.add(aa);
                }
                aa = find(value, 10, -1);
                if (arr[aa] == 0) {
                    arr[aa] = n;
                    list2.add(aa);
                }
                aa = find(value, 1, 1);
                if (arr[aa] == 0) {
                    arr[aa] = n;
                    list2.add(aa);
                }
                aa = find(value, 1, -1);
                if (arr[aa] == 0) {
                    arr[aa] = n;
                    list2.add(aa);
                }
            }
            list = list2;
            list2 = new ArrayList<>(10000);
            n++;
        }

        return -1;
    }

    private int find(int value, int c, int flag) {
        int v = value % (c * 10) / c;
        int r;
        if (v == 9 && flag == 1) {
            r = value - 9 * c;
        } else if (v == 0 && flag == -1) {
            r = value + 9 * c;
        } else {
            r = value + c * flag;
        }
        return r;
    }
}
